#include <string>
#include <vector>
#include <stack>

using namespace std;


/**
 * @brief 32. 最长有效括号
 * https://leetcode.cn/problems/longest-valid-parentheses/
 */
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<bool> flags(n, false);
        stack<int> stk;

        // Using stack for marking valid brackets
        for (int i=0; i<n; i++) {
            char c = s[i];
            if (stk.empty() && c == ')') continue;
            if (c == '(') {
                stk.push(i);
            } else if (c == ')') {
                flags[stk.top()] = true;
                flags[i] = true;
                stk.pop();
            }
        }

        // Record longest running 1's
        int running = 0, maxlen = 0;
        for (int i=0; i<n; i++) {
            if (flags[i]) {
                running++;
                maxlen = max(maxlen, running);
            } else {
                running = 0;
            }
        }

        return maxlen;
    }
};
